#include<iostream>
#include <stdlib.h>
#include <time.h>
#include<windows.h>
using namespace std;

//欢迎界面函数
void welcom() {

	cout << "*****欢迎使用银行模拟系统*****" << endl;

	cout << "银行的营业时间为 9：00-17：00" << endl;
//    cout << "本银行共 K 个窗口" << endl;
}


// 定义链表节点
template<class T>
struct Node {
	// 数据成员
	T element;
	Node<T> *next;

	//方法
	Node() {}

	Node(const T& element) {

		this->element = element;

	}

	Node(const T& element, Node<T> *next) {

		this->element = element;

		this->next = next;
	}
};

//定义队列
template<class T>
class queue {

	public:

		queue();       //初始化队列

		~queue() {};   //析构函数

		bool empty() { //判断队列是否为空

			return QueueSize == 0;

		}

		int size() {   //返回队列中元素的个数

			return QueueSize;

		}

		T& front() {   //返回队列首元素

			return Front->element;

		}
		T& back() {    //返回队列尾元素

			return Rear->element;

		}
		Node<T> * begin() {

			return Front;

		}
		void pop();    //删除首元素

		void push(const T& theElement);
	private:

		int QueueSize;        //队列长度

		Node<T> *Front;  //指向队列第一个元素的指针

		Node<T> *Rear;   //指向队列最后一个元素的指针
};

template<class T>
queue<T>::queue() {

	Front = Rear = NULL;

	QueueSize = 0;
}

template<class T>
void queue<T>::pop() {

	if (Front == NULL) {

		cout << "队列是空的";

		return;
	}
	Node<T> *nextNode = Front->next;

	delete Front;

	Front = nextNode;

	QueueSize--;
}

template<class T>
void queue<T>::push(const T& theElement) {

	//申请新元素节点
	Node<T> *newNode = new Node<T>(theElement, NULL);
	//把新节点插入队尾
	if (QueueSize == 0)  Front = newNode; //队空

	else  Rear->next = newNode;        //队非空

	Rear = newNode;

	QueueSize++;
}

//定义时间
struct Time {
	int h;  //时
	int min;  //分
};

//定义每个客户的到达银行时间，等待时间，开始办理业务时间，业务处理时间，结束业务时间(离开银行时间)
struct customers {

	int number;             //客户进入银行的序号

	struct Time ArrTime;     //到达银行时间

	struct Time WaitTime;       //等待时间

	struct Time StartTime;      //开始办理业务时间

	int WorkTime;              //业务处理时间(假设业务处理时间为整数，且处理时间范围为10-40min)

	struct Time EndTime;        //结束办理业务时间

};

//展示窗口服务情况
void ShowQueue(queue<customers> CusQueue[], int K) {

	Sleep(300);

	for (int i = 0; i < K; i++) {

		cout << "窗口" << i + 1 << ":";

		Node<customers> *m = CusQueue[i].begin();

		while (m != NULL) {

			cout << "客户" << m->element.number << " ";

			m = m->next;

		}
		cout << endl;
	}
	cout << endl;
}

//用户到达银行时间表函数
void CusTime(customers &c) {      //struct customers &c
	//随机产生客户到达银行时间
	c.ArrTime.h = 9 + rand() % 8;

	c.ArrTime.min = rand() % 60;

}

//按用户的到达时间将用户的先后顺序进行排序（由于用户的到达时间是随机产生的）
void CusSort(customers customer[], int N) {

	int MaxTimeIndex;   //记录客户到达的最晚时间对应的下标

	customers MaxTimeCus, SwapCus;

	//采用选择排序进行排序
	for (int i = N - 1; i > 0; i--) {
		MaxTimeCus = customer[i];

		MaxTimeIndex = i;
		//找出到达时间最晚的
		for (int j = 0; j < i; j++) {
			if ((customer[j].ArrTime.h) * 60 + customer[j].ArrTime.min > (MaxTimeCus.ArrTime.h) * 60 + MaxTimeCus.ArrTime.min) {
				MaxTimeCus = customer[j];

				MaxTimeIndex = j;
			}
		}
		if (i != MaxTimeIndex) {
			//swap部分
			SwapCus = customer[i];

			customer[i] = MaxTimeCus;

			customer[MaxTimeIndex] = SwapCus;

		}
	}

}

//判断客户需要去哪个窗口排队,即算出等待时间最少的队列
int WhereGo(queue<customers> CusQueue[], customers &customer, int EachQueueCusNumber[], int K) {
	//将用户在每个队列需要等待的时间放在一个数组里
	int EachQueueWaitTime[K];

	for (int i = 0; i < K; i++) {
		//客户的等待时间取决于他队伍最后一个人的结束办理时间
		int WaitTime = CusQueue[i].back().EndTime.h - customer.ArrTime.h;

		EachQueueWaitTime[i] = WaitTime * 60 + CusQueue[i].back().EndTime.min - customer.ArrTime.min;
	}
	//找出需要时间最少的队列
	int MinTimeQueueIndex = 0;

	for (int j = 1; j < K; j++) {

		if (EachQueueWaitTime[j] < EachQueueWaitTime[MinTimeQueueIndex])

			MinTimeQueueIndex = j;
	}

	//随机产生客户业务处理时间
	customer.WorkTime = 10 + rand() % 31;

	customer.WaitTime.h = EachQueueWaitTime[MinTimeQueueIndex] / 60;

	customer.WaitTime.min = EachQueueWaitTime[MinTimeQueueIndex] % 60;

	customer.StartTime.h = CusQueue[MinTimeQueueIndex].back().EndTime.h;

	customer.StartTime.min = CusQueue[MinTimeQueueIndex].back().EndTime.min;

	customer.EndTime.h = customer.StartTime.h + (customer.StartTime.min + customer.WorkTime) / 60;

	customer.EndTime.min = (customer.StartTime.min + customer.WorkTime) % 60;
	//将客户加入队列
	//对银行关门时间到了，还在办理的客户允许继续办理完业务再离开，还在排队的客户马上离开
	if ((customer.StartTime.h) * 60 + customer.StartTime.min < 14 * 60) {

		CusQueue[MinTimeQueueIndex].push(customer);

		EachQueueCusNumber[MinTimeQueueIndex]++;
	}

	return MinTimeQueueIndex;
}

//判断下一个客户到来时哪个队列的队首客户是否已经办理完业务，并进行出队
void LeaveQueue(queue<customers> CusQueue[], customers customer, int K) {

	for (int i = 0; i < K; i++) {

		while (!CusQueue[i].empty() && (CusQueue[i].front().StartTime.h) * 60 + CusQueue[i].front().StartTime.min +

		        CusQueue[i].front().WorkTime <= (customer.ArrTime.h) * 60 + customer.ArrTime.min)  {

			cout << "----------客户" << CusQueue[i].front().number << "离开了窗口" << i + 1 << "----------" << endl;

			CusQueue[i].pop();

		}
	}
}

//用户进入队列函数
void cusInQueue(queue<customers> CusQueue[], customers customer[], int EachQueueCusNumber[], int N, int K) {
	//判断哪个窗口是空闲的
	int QueueNumber;

	for (int i = 0; i < N; i++) {

		bool QueueFree = false;

		//每次进入队列判断各队首是否已经办理完业务
		LeaveQueue(CusQueue, customer[i], K);

		for (int j = 0; j < K; j++) {
			//窗口中有空闲的情况
			if (CusQueue[j].empty()) {
				//客户每进入一个队列都需要判断每个队首客户是否已经办理完业务
				customer[i].WorkTime = 10 + rand() % 31;

				customer[i].WaitTime.h = 0;

				customer[i].WaitTime.min = 0;

				customer[i].StartTime.h = customer[i].ArrTime.h;

				customer[i].StartTime.min = customer[i].ArrTime.min;

				customer[i].EndTime.h = customer[i].StartTime.h + (customer[i].StartTime.min + customer[i].WorkTime) / 60;

				customer[i].EndTime.min = (customer[i].StartTime.min + customer[i].WorkTime) % 60;

				CusQueue[j].push(customer[i]);

				EachQueueCusNumber[j]++;

				QueueFree = true;

				cout << "----------客户" << customer[i].number << "到达了窗口" << j + 1 << "----------" << endl;

				cout << "客户" << customer[i].number << "需等人数：0" << endl;

				break;
			}
		}
		//窗口中没有空闲的情况
		if (QueueFree == false) {

			QueueNumber = WhereGo(CusQueue, customer[i], EachQueueCusNumber, K); //判断哪个队列的等待时间最少

			cout << "----------客户" << customer[i].number << "到达了窗口" << QueueNumber << "----------" << endl;

			cout << "客户" << customer[i].number << "需等人数：" << CusQueue[QueueNumber].size() - 1 << endl;

		}
		ShowQueue(CusQueue, K);
	}
	//展示最后客户的离开状态
	LeaveQueue(CusQueue, customer[N], K);

	ShowQueue(CusQueue, K);
}

void Show(queue<customers> CusQueue[], customers customer[], int EachQueueCusNumber[], int N, int K) {

	for (int i = 0; i < N; i++) {
		Sleep(200);
		CusTime(customer[i]);       //初始用户时间

		EachQueueCusNumber[i] = 0;        //初始窗口服务客户个数

		cout << i + 1 << " 顾客到达时间: " << customer[i].ArrTime.h << ": ";

		cout << customer[i].ArrTime.min << endl;
	}

	CusSort(customer, N); //按客户进入银行的先后顺序进行排序

	cout << "---------------------------after sort---------------------------" << endl;

	for (int i = 0; i < N; i++) {
		Sleep(200);
		customer[i].number = i + 1;

		cout << i + 1 << " 顾客到达时间: " << customer[i].ArrTime.h << ": " << customer[i].ArrTime.min << endl;

	}
}

void List(queue<customers> CusQueue[], customers customer[], int N) {

	for (int i = 0; i < N; i++) {

		cout << i + 1;

		cout << " 顾客到达时间: " << customer[i].StartTime.h << ":" << customer[i].StartTime.min << "\t";

		cout << " 顾客离开时间: " << customer[i].EndTime.h << ":" << customer[i].EndTime.min << "\t";

		cout << " 办理业务时间: " << customer[i].WorkTime << "min\t";

		cout << " 等待时间: " << (customer[i].WaitTime.h) * 60 + customer[i].WaitTime.min << " " << endl;

	}
}

void StopTime(customers customer[], int N) {

	int MaxCusWaitTime = (customer[0].WaitTime.h) * 60 + customer[0].WaitTime.min;

	for (int i = 1; i < N; i++) {

		if ((customer[i].WaitTime.h) * 60 + customer[i].WaitTime.min > MaxCusWaitTime)

			MaxCusWaitTime = (customer[i].WaitTime.h) * 60 + customer[i].WaitTime.min;

	}

	//输出一天客户在银行的平均逗留时间  首先算出每个人在银行的总时间，然后求和，然后除以一天的客户总数
	int WaitWorkTime = 0;

	for (int j = 0; j < N; j++) {

		WaitWorkTime = customer[j].WorkTime + (customer[j].WaitTime.h) * 60 + customer[j].WaitTime.min + WaitWorkTime;

	}

	if (N == 0)

		cout << "一天客户在银行的平均逗留时间为:" << 0 << "min" << endl;

	else

		cout << "一天客户在银行的平均逗留时间为:" << (double)WaitWorkTime / N << "min" << endl;

	cout << endl;

	cout << "最久等待时间: " << MaxCusWaitTime << "min" << endl;
}

void ServeNumber(int EachQueueCusNumber[], int N, int K) {

	//每个窗口每天办理的客户数
	int ActualCusNumbers = 0;

	if (N == 0) {
		for (int i = 0; i < K; i++) { //0 1 2 3

			cout << "窗口" << i + 1 << "服务顾客个数: " << 0 << endl;

		}
	} else {
		for (int i = 0; i < K; i++) {

			cout << "窗口" << i + 1 << "服务顾客个数: " << EachQueueCusNumber[i] << endl;

			ActualCusNumbers += EachQueueCusNumber[i];
		}
	}
}

int main() {
	srand(time(0));
	srand((unsigned int)time(NULL));  //使每次编译完后产生的随机数不同

	welcom();   //欢迎界面

	//定义银行服务窗口个数和一天的客户人数
	int K;
//	printf ("请输入窗口个数：");
//	scanf ("%d", &K);
	K = rand() % 10 + 1;
	cout << "本银行共 " << K << " 个窗口" << endl;

	int N = 60 + rand() % 30;   //客户人数
	cout << endl;
	cout << "您选的号码为：" << N << endl;
	getchar();

	cout << endl;

	customers customer[N];

	queue<customers> CusQueue[K];

	int EachQueueCusNumber[N];

	Show(CusQueue, customer, EachQueueCusNumber, N, K); //展示客户

	cout << "---------------------------begin serve---------------------------" << endl;

	cusInQueue(CusQueue, customer, EachQueueCusNumber, N, K); //客户进队列

	cout << "---------------------------end serve---------------------------" << endl;

	cout << endl;

	cout << "---------------------------after customer in queue---------------------------" << endl;

	List(CusQueue, customer, N); //到达 等待 办理 离开 时间

	cout << endl;

	StopTime(customer, N); //客户平均滞留时间

	cout << endl;

	ServeNumber(EachQueueCusNumber, N, K);


	return 0;
}
